package Top_Interview_Questions_Review._005Divide_And_Conquer;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/3 11:57
 * <p>
 * 功能描述:
 */
public class _0240 {

    public static void main(String[] args) {
        _0240 test = new _0240();

        int[][] nums = {
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };

        test.searchMatrix1(nums,20);

    }


    /*--------------------------------------减而治之---------------------------------------*/

    /**
     * 如果选择左下角为起点，以下展示了“减治”的过程。
     * https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/er-fen-fa-pai-chu-fa-python-dai-ma-java-dai-ma-by-/
     */
    public boolean searchMatrix1(int[][] matrix, int target) {
        int rows = matrix.length;
        if (rows == 0) {
            return false;
        }
        int cols = matrix[0].length;
        if (cols == 0) {
            return false;
        }


        // 起点：左下角
        int x = rows - 1;
        int y = 0;
        // 不越界的条件是：行大于等于 0，列小于等于 cols - 1
        while (x >= 0 && y < cols) {
            // 打开注释，可以用于调试的代码
             System.out.println("沿途走过的数字：" + matrix[x][y]);
            if (matrix[x][y] > target) {
                x--;
            } else if (matrix[x][y] < target) {
                y++;
            } else {
                return true;
            }
        }
        return false;
    }
    /*-------------------------------------------------------------------------------------*/

}
